home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / basic / _array.c next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  8.2 KB  |  447 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _array.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/impl/gen_array.h>
  17.  
  18. #define SWAP(a,b) { register GenPtr help = *a; *a = *b; *b = help; }
  19.  
  20. #define MIN_D 16 
  21.  
  22. void gen_array::read(istream& in, string s)
  23. { cout << s;
  24.   int i = 0; 
  25.   while (in && i<sz)
  26.   { clear_entry(v[i]);
  27.     read_el(v[i],in);
  28.     i++;
  29.    }
  30.  }
  31.  
  32. void gen_array::print(ostream& out, string s, char space) const
  33. { cout << s;
  34.   int i = 0; 
  35.   while (i < sz)
  36.     { out << string("%c",space);
  37.       print_el(v[i],out); 
  38.       i++;
  39.      }
  40.   out.flush();
  41. }
  42.  
  43. void gen_array::clear() 
  44. { register int i = sz;
  45.   register GenPtr* vv = &v[i];
  46.   while (i--) clear_entry(*--vv);
  47. }
  48.  
  49. void gen_array::init() 
  50. { register int i = sz;
  51.   register GenPtr* vv = &v[i];
  52.   while (i--) init_entry(*--vv);
  53. }
  54.  
  55. gen_array::gen_array()
  56. { Low = 0;
  57.   High = -1;
  58.   sz = 0;
  59.   v = 0;
  60. }
  61.  
  62.  
  63. gen_array::gen_array(int a, int b)
  64. { if (a>b) error_handler(1,"bad array size");
  65.   Low = a;
  66.   High = b;
  67.   sz = b-a+1;
  68.   v = new GenPtr[sz+1];
  69.   if (v==0) error_handler(99,"array: out of memory");
  70.   register int i = sz;
  71.   register GenPtr* vv = &v[i];
  72.   while (i--) init_entry(*--vv);
  73.  }
  74.  
  75. gen_array::gen_array(int n)
  76. { Low = 0;
  77.   High = n-1;
  78.   sz = n;
  79.   v = new GenPtr[sz+1];
  80.   if (v==0) error_handler(99,"array: out of memory");
  81.   register int i = sz;
  82.   register GenPtr* vv = &v[i];
  83.   while (i--) init_entry(*--vv);
  84. }
  85.  
  86. gen_array::gen_array(const gen_array& a)
  87. { register i = a.sz;
  88.   sz = i;       
  89.   Low = a.Low;
  90.   High = a.High;
  91.   v = new GenPtr[i+1];
  92.   register GenPtr* vv = &v[i];
  93.   register GenPtr* av = &a.v[i];
  94.   while (i--) 
  95.   { *--vv = *--av;
  96.     copy_entry(*vv);
  97.    }
  98. }
  99.  
  100. gen_array& gen_array::operator=(const gen_array& a)
  101. { if (this != &a)
  102.   { register i = a.sz;
  103.     if (sz != i)
  104.     { sz = i;       
  105.       clear();
  106.       delete v;
  107.       v = new GenPtr[i+1];
  108.     }
  109.     Low = a.Low;
  110.     High = a.High;
  111.     register GenPtr* vv = &v[i];
  112.     register GenPtr* av = &a.v[i];
  113.     while (i--) 
  114.     { *--vv = *--av;
  115.       copy_entry(*vv);
  116.      }
  117.   }
  118.  return *this;
  119. }
  120.  
  121. void gen_array::permute(int l, int r)
  122. {
  123.   if (l<Low || l>High || r<l || r>High) 
  124.          error_handler(2,"array::permute illegal range");
  125.  
  126.   l -= Low;
  127.   r -= Low;
  128.  
  129.   register GenPtr* x;
  130.   register GenPtr* y;
  131.   register GenPtr* stop = v+r+1;
  132.  
  133.   init_random();
  134.   for(x=v+l;x!=stop;x++) 
  135.   { y = v+random(l,r);  
  136.     SWAP(x,y);  
  137.    }
  138. }
  139.  
  140. static int min_d;
  141.  
  142. void gen_array::quick_test(GenPtr* l, GenPtr* r)
  143. { 
  144.   register GenPtr  s;
  145.   register GenPtr* k;
  146.   register GenPtr* i = l+random()%(r-l);
  147.  
  148.   SWAP(i,l);
  149.   i = l;
  150.   k = r+1;
  151.   s = *l;
  152.  
  153.   for(;;)
  154.   { while (*(++i) < s);
  155.     while (*(--k) > s);
  156.     if (i<k) SWAP(i,k) else break;
  157.    }
  158.  
  159.   SWAP(l,k);
  160.  
  161.   if (l < k-min_d) quick_test(l,k-1);
  162.   if (r > k+min_d) quick_test(k+1,r);
  163. }
  164.  
  165. void gen_array::sort_test(int d) 
  166. {
  167.   GenPtr* left  = v;
  168.   GenPtr* right = v+sz-1;
  169.   GenPtr* min_stop = left + d;
  170.  
  171.   if (min_stop > right) min_stop = right;
  172.  
  173.   v[sz] = GenPtr(MAXINT);
  174.  
  175.   min_d = d;
  176.   quick_test(left,right);
  177.   if (d>1) int_insertion_sort(left,right,min_stop);
  178.  }
  179.  
  180.  
  181. void gen_array::sort(int l, int h, CMP_PTR f) 
  182. {
  183.   GenPtr* left  = v+l-Low;
  184.   GenPtr* right = v+h-Low;
  185.   GenPtr* min_stop = left + MIN_D;
  186.  
  187.   if (min_stop > right) min_stop = right;
  188.  
  189.   if (f)
  190.      { quick_sort(left,right,f);
  191.        insertion_sort(left,right,min_stop,f);
  192.       }
  193.   else
  194.      if (int_type())
  195.       { int_quick_sort(left,right);
  196.         int_insertion_sort(left,right,min_stop);
  197.        }
  198.      else
  199.        { quick_sort(left,right);
  200.          insertion_sort(left,right,min_stop);
  201.         }
  202.  }
  203.  
  204.  
  205. void gen_array::quick_sort(GenPtr* l, GenPtr* r)
  206. { 
  207.   register GenPtr* i = l+(r-l)/2; //l+random()%(r-l);
  208.   register GenPtr* k;
  209.  
  210.   if (cmp(*i,*r) > 0) SWAP(i,r);
  211.   SWAP(l,i);
  212.  
  213.   GenPtr  s = *l;
  214.  
  215.   i = l;
  216.   k = r;
  217.  
  218.   for(;;)
  219.   { while (cmp(*(++i),s)<0);
  220.     while (cmp(*(--k),s)>0);
  221.     if (i<k) SWAP(i,k) else break;
  222.    }
  223.  
  224.   SWAP(l,k);
  225.  
  226.   if (k > l+MIN_D) quick_sort(l,k-1);
  227.   if (r > k+MIN_D) quick_sort(k+1,r);
  228. }
  229.  
  230.  
  231. void gen_array::quick_sort(GenPtr* l, GenPtr* r, CMP_PTR usr_cmp)
  232. { 
  233.   register GenPtr* i = l+(r-l)/2; //l+random()%(r-l);
  234.   register GenPtr* k;
  235.  
  236.   if (usr_cmp(*i,*r) > 0) SWAP(i,r);
  237.   SWAP(l,i);
  238.  
  239.   GenPtr  s = *l;
  240.  
  241.   i = l;
  242.   k = r;
  243.  
  244.   for(;;)
  245.   { while (usr_cmp(*(++i),s)<0);
  246.     while (usr_cmp(*(--k),s)>0);
  247.     if (i<k) SWAP(i,k) else break;
  248.    }
  249.  
  250.   SWAP(l,k);
  251.  
  252.   if (k > l+MIN_D) quick_sort(l,k-1,usr_cmp);
  253.   if (r > k+MIN_D) quick_sort(k+1,r,usr_cmp);
  254. }
  255.  
  256.  
  257. void gen_array::int_quick_sort(GenPtr* l, GenPtr* r)
  258. { 
  259.   register GenPtr* i = l+(r-l)/2; //l+random()%(r-l);
  260.   register GenPtr* k;
  261.  
  262.   if (*i > *r) SWAP(i,r);
  263.   SWAP(l,i);
  264.  
  265.   GenPtr  s = *l;
  266.  
  267.   i = l;
  268.   k = r;
  269.  
  270.   for(;;)
  271.   { while (*(++i) < s);
  272.     while (*(--k) > s);
  273.     if (i<k) SWAP(i,k) else break;
  274.    }
  275.  
  276.   SWAP(l,k);
  277.  
  278.   if (k > l+MIN_D) int_quick_sort(l,k-1);
  279.   if (r > k+MIN_D) int_quick_sort(k+1,r);
  280. }
  281.  
  282. void gen_array::insertion_sort(GenPtr* l, GenPtr* r, GenPtr* min_stop, 
  283.                                CMP_PTR usr_cmp)
  284. {
  285.   register GenPtr* min=l;
  286.   register GenPtr* run;
  287.   register GenPtr* p;
  288.   register GenPtr* q;
  289.  
  290.   for (run = l+1; run <= min_stop; run++)
  291.       if (usr_cmp(*run,*min) < 0) min = run;
  292.  
  293.   SWAP(min,l);
  294.  
  295.   if (r == l+1) return;
  296.  
  297.   for(run=l+2; run <= r; run++)
  298.   { for (min = run-1; usr_cmp(*run,*min) < 0; min--);
  299.     min++;
  300.     if (run != min) 
  301.     { GenPtr save = *run;
  302.       for(p=run, q = run-1; p > min; p--,q--) *p = *q;
  303.       *min = save;
  304.      }
  305.    }
  306. }
  307.  
  308.  
  309. void gen_array::insertion_sort(GenPtr* l, GenPtr* r, GenPtr* min_stop)
  310. {
  311.   register GenPtr* min=l;
  312.   register GenPtr* run;
  313.   register GenPtr* p;
  314.   register GenPtr* q;
  315.  
  316.   for (run = l+1; run <= min_stop; run++)
  317.       if (cmp(*run,*min) < 0) min = run;
  318.  
  319.   SWAP(min,l);
  320.  
  321.   if (r == l+1) return;
  322.  
  323.   for(run=l+2; run <= r; run++)
  324.   { for (min = run-1; cmp(*run,*min) < 0; min--);
  325.     min++;
  326.     if (run != min) 
  327.     { GenPtr save = *run;
  328.       for(p=run, q = run-1; p > min; p--,q--) *p = *q;
  329.       *min = save;
  330.      }
  331.    }
  332. }
  333.  
  334.  
  335.  
  336. void gen_array::int_insertion_sort(GenPtr* l, GenPtr* r, GenPtr* min_stop)
  337. {
  338.   register GenPtr* min=l;
  339.   register GenPtr* run;
  340.   register GenPtr* p;
  341.   register GenPtr* q;
  342.  
  343.   for (run = l+1; run <= min_stop; run++)
  344.       if (*run <  *min) min = run;
  345.  
  346.   SWAP(min,l);
  347.  
  348.   if (r == l+1) return;
  349.  
  350.   for(run=l+2; run <= r; run++)
  351.   { for (min = run-1; *run < *min; min--);
  352.     min++;
  353.     if (run != min) 
  354.     { GenPtr save = *run;
  355.       for(p=run, q = run-1; p > min; p--,q--) *p = *q;
  356.       *min = save;
  357.      }
  358.    }
  359. }
  360.  
  361.  
  362.  
  363.  
  364. int gen_array::binary_search(GenPtr x)
  365. { int l = 0;
  366.   int r = sz-1;
  367.   int m;
  368.   while (l<r)
  369.   { m = (l+r)/2;
  370.     if (cmp(x,elem(m))==0) { l = m; break; }
  371.     if (cmp(x,elem(m)) > 0) l = m+1;
  372.     else
  373.     if (cmp(x,elem(m)) < 0) r = m-1;
  374.    }
  375.  
  376.   return  (cmp(elem(l),x)==0) ? (l+Low) : (Low-1);
  377. }
  378.  
  379. int gen_array::binary_search(GenPtr x, CMP_PTR usr_cmp)
  380. { int l = 0;
  381.   int r = sz-1;
  382.   int m;
  383.   while (l<r)
  384.   { m = (l+r)/2;
  385.     if (usr_cmp(x,elem(m))==0) { l = m; break; }
  386.     if (usr_cmp(x,elem(m)) > 0) l = m+1;
  387.     else
  388.     if (usr_cmp(x,elem(m)) < 0) r = m-1;
  389.    }
  390.  
  391.   return  (usr_cmp(elem(l),x)==0) ? (l+Low) : (Low-1);
  392. }
  393.  
  394. int gen_array::int_binary_search(GenPtr x)
  395. { int l = 0;
  396.   int r = sz-1;
  397.   int m;
  398.   while (l<r)
  399.   { m = (l+r)/2;
  400.     if (x ==elem(m)) { l = m; break; }
  401.     if (x > elem(m)) 
  402.        l = m+1;
  403.     else
  404.        if (x < elem(m)) r = m-1;
  405.    }
  406.  
  407.   return  (elem(l) == x) ? (l+Low) : (Low-1);
  408. }
  409.  
  410.  
  411.  
  412. void gen_array2::init(int a, int b, int c, int d)
  413. { register int i,j;
  414.   for (i=a;i<=b;i++) 
  415.       for (j=c; j<=d; j++) init_entry(row(i)->entry(j));
  416. }
  417.  
  418. gen_array2::gen_array2(int a, int b, int c, int d) : A(a,b) 
  419. { Low1  = a;
  420.   High1 = b;
  421.   Low2  = c;
  422.   High2 = d;
  423.   while (b>=a) A.entry(b--) = (GenPtr) new gen_array(c,d); 
  424. }
  425.  
  426. gen_array2::gen_array2(int a, int b) : A(a) 
  427. { Low1  = 0;
  428.   High1 = a-1;
  429.   Low2  = 0;
  430.   High2 = b-1;
  431.   while (a>0) A.entry(--a) = (GenPtr) new gen_array(b); 
  432. }
  433.  
  434. void gen_array2::clear()
  435. { register int i,j;
  436.   for (i=Low1;i<=High1;i++) 
  437.   for (j=Low2;j<=High2;j++) 
  438.   clear_entry(row(i)->entry(j));
  439. }
  440.  
  441. gen_array2::~gen_array2()
  442. { register int i;
  443.   for (i=Low1;i<=High1;i++) delete (gen_array*)A.entry(i);
  444. }
  445.  
  446.  
  447.